package zuochengyun;

//打印N个数组中的Top K个数
//这N个数组可能长度不一
public class TopKNumberOfNArrays {

	public static void main(String[] args) {
		
	}
	
	//使用堆的方式来完成
	private class HeapNode{
		public int value;  //值
		public int arrNo;  //来自哪个数组
		public int index;  //在数组中的下标
		
		public HeapNode(int value, int arrNo, int index) {
			super();
			this.value = value;
			this.arrNo = arrNo;
			this.index = index;
		}
	}
	
	//N个数组都是有序的
	public void printTopK(int[][] matrix, int k){
		//首先建立一个N个元素的堆
		int heapSize = matrix.length;
		HeapNode[] heap = new HeapNode[heapSize];
		for (int i = 0; i < heap.length; i++) {
			//所有的数组都是有序的，首先将最后一个数组放入堆中
			int index = matrix[i].length - 1;
			heap[i] = new HeapNode(matrix[i][index], i, index);
			heapCreate(heap, i);
		}
		System.out.println("Top " + k + " : ");
		for (int i = 0; i < k; i++) {
			if(heapSize == 0){
				break;
			}
			//大根堆，直接输出堆的第一个元素
			System.out.println(heap[0].value + " ");
			//index为0表示这个数组中的有元素全部加入了，此时交换堆头与堆尾的元素
			if(heap[0].index != 0){
				heap[0].value = matrix[heap[0].arrNo][heap[0].index--];
			}else{
				swap(heap, 0, --heapSize);
			}
			//调整堆
			heapAdjust(heap, 0, heapSize);
		}
	}
	
	
	private void heapAdjust(HeapNode[] heap, int index, int heapSize) {
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int large = index;
		while(left < heapSize){
			if(heap[left].value > heap[index].value){
				large = left;
			}
			if(right < heapSize && heap[right].value > heap[left].value){
				large = right;
			}
			if(large != index){
				swap(heap, index, large);
			}else {
				break;
			}
			index = large;
			left = index * 2 + 1;
			right = index * 2 + 2;
		}
	}


	public void heapCreate(HeapNode[] heap, int index){
		while(index != 0){
			int parent = (index - 1) / 2;
			if(heap[parent].value < heap[index].value){
				swap(heap, parent, index);
				index = parent;
			}else{
				break;
			}
		}
	}

	public void swap(HeapNode[] heap, int parent, int index) {
		HeapNode temp = heap[parent];
		heap[parent] = heap[index];
		heap[index] = temp;
	}
	
	
}
